import datetime
import math
import random
import sys
import time
import threading


class IndexedSet():
  def __init__(self, items=[]):
    self._set = set(items)
    self._list = list(self._set)
    self._map = {v: i for i, v in enumerate(self._list)}
  def __getitem__(self, key):
    return self._list[key]
  def __or__(self, other):
    return IndexedSet(self._set | other._set)
  def __sub__(self, other):
    return IndexedSet(self._set - other._set)
  def __update__(self, other):
    self._set |= other
    self._list = list(self.set)
    self._map = {k: v for k, v in enumerate(self._list)}
  def __getitem__(self, key):
    return self._list[key]
  def __iter__(self):
    return self._list.__iter__()
  def __len__(self):
    return self._list.__len__()
  def __repr__(self):
    return 'IndexedSet(' + str(self._list) + ')'
  def add(self, item):
    self._set.add(item)
    self._list = list(self._set)
    self._map = {v: i for i, v in enumerate(self._list)}
  def remove(self, item):
    self._set.remove(item)
    self._list = list(self._set)
    self._map = {v: i for i, v in enumerate(self._list)}
  def discard(self, item):
    if item in self._set:
      self.remove(item)
  def index(self, item):
    return self._map[item]

def set_choice(set):
  return random.sample(set, 1)[0]

def bits_required(n):
  if (n == 0):
    return 0
  else:
    # return math.ceil(math.log(n, 2))
    return math.log(n, 2)

def now():
  return datetime.datetime.now()

# Prints one of the following formats*:
# 1.58 days
# 2.98 hours
# 9.28 minutes # Not actually added yet, oops.
# 5.60 seconds
# 790 milliseconds
# *Except I prefer abbreviated formats, so I print d,h,m,s, or ms. 
def format_delta(start,end):

  # Time in microseconds
  one_day = 86400000000
  one_hour = 3600000000
  one_second = 1000000
  one_millisecond = 1000

  delta = end - start

  build_time_us = delta.microseconds + delta.seconds * one_second + delta.days * one_day

  days = 0
  while build_time_us > one_day:
    build_time_us -= one_day
    days += 1

  if days > 0:
    time_str = "%.2fd" % ( days + build_time_us / float(one_day) )
  else:
    hours = 0
    while build_time_us > one_hour:
      build_time_us -= one_hour
      hours += 1
    if hours > 0:
      time_str = "%.2fh" % ( hours + build_time_us / float(one_hour) )
    else:
      seconds = 0
      while build_time_us > one_second:
        build_time_us -= one_second
        seconds += 1
      if seconds > 0:
        time_str = "%.2fs" % ( seconds + build_time_us / float(one_second) )
      else:
        ms = 0
        while build_time_us > one_millisecond:
          build_time_us -= one_millisecond
          ms += 1
        time_str = "%.2fms" % ( ms + build_time_us / float(one_millisecond) )
  return time_str

class Timer:
  def __enter__(self):
    self.begin = now()

  def __exit__(self, type, value, traceback):
    print(format_delta(self.begin, now()))

import cProfile, pstats
class Profiler:
  def __enter__(self):
    self.pr = cProfile.Profile()
    self.pr.enable()

  def __exit__(self, type, value, traceback):
    self.pr.disable()
    sortby = 'cumulative'
    ps = pstats.Stats(self.pr, stream=stdout).sort_stats(sortby)
    ps.print_stats()
    print(s.getvalue())

class Logger:
  HEADER = '\033[95m'
  OKBLUE = '\033[94m'
  OKGREEN = '\033[92m'
  WARNING = '\033[93m'
  FAIL = '\033[91m'
  ENDC = '\033[0m'
  def __init__(self, filename=None):
    if not filename:
      filename = datetime.datetime.fromtimestamp(time.time()).strftime('%Y-%m-%d %H%M')
    self.terminal = sys.stdout
    self.log_file = open(filename, 'w')

  def log(self, message='', color=None):
    self.log_file.write(message + '\n')
    if color:
      message = color + message + Logger.ENDC
    message += '\n'
    if len(message) < 200:
      self.terminal.write(message)
    else:
      self.terminal.write(message[0:200] + '...')
    self.flush()
  
  def flush(self):
    self.log_file.flush()
    self.terminal.flush()